2023 DASCTF-0x401

Van1sh 比赛小屋 Write Up

创建时间:2023-07-23 00:00

字数:1.9k 阅读:

ezDHKE
ezRSA
EzAlgebra

周六一天都在看 ImaginaryCTF，被 maple 的题虐惨了都。猪脑过载的时候过来隔壁看看 DASCTF 的题，试图放松下脑汁。

ezDHKE

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import randbytes, getrandbits
from flag import flag
def diffie_hellman(g, p, flag):
    alice = getrandbits(1024) #私钥XA
    bob = getrandbits(1024)  # 私钥XB

    # g作为本原根              
    alice_c = pow(g, alice, p)   #p是共享素数 计算公钥YA  
    bob_c = pow(g, bob, p)        # 公钥YB
    print(alice_c , bob_c)
    # YB的XA次方 是Alice在计算共享密钥  digest获得摘要值
    key = sha256(long_to_bytes(pow(bob_c, alice, p))).digest()
    iv = b"dasctfdasctfdasc"
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc = aes.encrypt(flag)
    print(enc)

def getp():
    p = int(input("P = "))
    assert isPrime(p)
    assert p.bit_length() >= 1024 and p.bit_length() <= 2048
    g = 2
    diffie_hellman(g, p, flag)

getp()

很简单的一个 DHP，甚至题目代码都还有注释，贴心到家了。

题目的点在于模数 $p$ 是由我们自己控制的，虽然需要满足比特长度在 1024 和 2048 之间，但我们找一个光滑 $p$ ，然后就能解 DLP ，继而解 DHP 了。

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import choice


def myPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(sieve_base)
        if isPrime(n + 1):
            return n + 1

A = 
B = 
# p = myPrime(1024)
p = 515482686852905819026776471764664175154597541766196631808569599693945100129832449512555508593916309509882123983344422623771622319416757571580459907525933456572547127497459096961018073753946157799257464082944083244303912221051154205283779640770766245958565082104682846235618735174419474409835799563673915973399
A = Mod(A,p)
B = Mod(B,p)
key = pow(B,int(discrete_log(A,Mod(2,p))),p)
key = sha256(long_to_bytes(key)).digest()
c = b''
iv = b"dasctfdasctfdasc"
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(c)
print(flag)

ezRSA

from Crypto.Util.number import *
from secret import secret, flag
def encrypt(m):
    return pow(m, e, n)
assert flag == b"dasctf{" + secret + b"}"
e = 11
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)
print(N, gift, pow(n, e, N))
print(encrypt(bytes_to_long(secret)),
    encrypt(bytes_to_long(flag)))

# 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
# 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

题目套了两次，我们先解第二层获取第一层的 $n$，看到 gift = P ^ (Q >> 16)，首先由于 $Q$ 右移了 16 位，所以 $P$ 的高位是泄露出来了的。我们拿着 $P$ 的高位，用 $N$ 除，是能获取 $Q$ 的高位的，本地可以测试一下先

from Crypto.Util.number import *
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)


# gift 泄露了 P 的高16比特

Pbar =  gift >>(512-16)
print(P >>(512-16))
print(Pbar)

# 根据 Pbar 和 N 获取 Q 的高位
Qbar = (N>>(1024-32)) // Pbar
print(Q>>(512-16))
print(Qbar)

但是注意到，我们会发现 Qbar 和 Q>>(512-16) 由于整除会有 1 - 2 的误差，所以为了尽可能减少这些判断的条件，我们索性就把低位抛弃掉，少恢复一些（我这里直接丢了 6 比特）。有了 Q 的高位，我们就能再利用 gift，和它异或，恢复 P 的高位，如此循环往复

nc = 
secret_c = 
flag_c = 

pbar = gift >>(512-16)

while True:
	try:
		qbar = (N>>(1024 - pbar.bit_length()*2))//pbar
		#print(qbar)
		qbar = qbar>>6
		gifts = gift^(qbar<<(512-16-qbar.bit_length()))
		pbar = gifts >> (512-16-qbar.bit_length())
		#print(pbar,pbar.bit_length())
	except:
		break

这个粗暴的循环最后会还剩大约6个比特没有恢复，我们再附上一个暴力搜索就可以了。

for i in range(64):
	if N%((pbar<<6)+i) == 0:
		p = (pbar<<6)+i
		q = N//p
		print("[+] p =",p)
		print("[+] q =",q)
		break

拿到 P,Q 之后我们就能恢复 n 了

e = 11
nc = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
d = inverse(e,(p-1)*(q-1))

n = pow(nc,d,N)
print(n)

注意到一个问题，就是我们算出 $n$ 之后，最好拿去 factordb 查一下，我们会发现这个直接出来的 $n$ 有一些小因子（甚至还是一个偶数），所以真正的 $n$ 应该比 $N$ 大，所以这里我们还要再 $n+N$ 一下，再拿去差就是啥也查不到了。

接下来我们需要解第一层，第一层的问题总结起来很简单，就是两个式子
$$
f1: flag^e \equiv c_1 \pmod n
$$

$$
f2:secret^e \equiv c_2 \pmod n
$$

其中明文相关，flag == b"dasctf{" + secret + b"}"，可能部分选手会不知道怎么用数字表示 $flag$ 和 $secret$ 的关系，可以分开来理解，

如果 flag == secret + b"}" 那么我们知道一个字符占一个字节，表示在十进制上，就是把 $secret$ 向左移动一个字节，其实也就是 $256 \cdot secret+125$。

低位很好表示，那么高位呢？如果我们知道 secret 的长度，其实就是 "dasctf{" 向左移动 secret 的长度 + 1 个字节，也就是 $dasctf \cdot 256^{len(secret)+1} $

因此结合起来，我们就可以将两条式子表示为

1 2	f1 = (bytes_to_long(b"dasctf{" + b"\x00"i + b"}") + 256x)^11 - flag_c # i 表示 secret 的长度, x 表示 secret f2 = x^11 - secret_c

然后就是明文相关攻击了，我们知道 $x=secret$ 肯定是这两个方程的解，于是这两个式子肯定有公因式 $(x-secret)$

from Crypto.Util.number import *
def GCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return GCD(b, a % b)

N = 83410392685813224685786027640778560521035854332627839979281105731457044069408118952629284089869335506983096270269822559619624906180108256504440296527471536363057103101146262613593336072556587341466840510200003498265457285439149541137127199088938421905041387224795918868443175561632999479925818053898100117419
R.<x> = Zmod(N)[]
secret_c = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
flag_c = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

for i in range(40):
	f1 = (bytes_to_long(b"dasctf{" + b"\x00"*i + b"}") + 256*x)^11 - flag_c
	f2 = x^11 - secret_c
	if (N-GCD(f1,f2).coefficients()[0]) != N-1:
		print(long_to_bytes(int(N-GCD(f1,f2).coefficients()[0])))
# b'C0pper_Sm1th_Mak3s_T1ng5_Bet4er'

EzAlgebra

from Crypto.Util.number import getPrime, bytes_to_long

def YiJiuJiuQiNian(Wo, Xue, Hui, Le, Kai):
    Qi = 1997
    Che = Wo+Hui if Le==1 else Wo*Hui
    while(Xue):
        Qi += (pow(Che, Xue, Kai)) % Kai
        Xue -= 1
    return Qi
    
l = 512
m = bytes_to_long(flag)
p = getPrime(l)
q = getPrime(l//2)
r = getPrime(l//2)
n = p * q * r
t = getrandbits(32)
c1 = YiJiuJiuQiNian(t, 4, p, 1, n)
c2 = YiJiuJiuQiNian(m, 19, t, 0, q)
c3 = YiJiuJiuQiNian(m, 19, t, 1, q)
print(f"n = {n}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")

看到这个函数名字就知道是 1997年（不知道的朋友可以看一下前面 2023CCTF 的推文，或者 ctftime 上搜一下）的队友整活了。

抛开“混淆”的过程，我们可以把题目归结为两个问题，首先第一个，

我们有 $c \equiv (t+p)^4+(t+p)^3+(t+p)^2+(t+p)+1997 \pmod n $

那么看到式子 degree 怎么低，又有 $p$，很难不去用 copper 啊

我们有 $c \equiv t^4+t^3+t^2+t+1997 \pmod p$

于是

N = 54743202946161502811856295720870810456365343228950644705855322505182442571262980076941089058115540911930788333918940031879968906218781504935426145280173361374496692033334841657192812883322298846746060682411659733228146767637511270445829110291022551957289461462065489646257622668554123931913354561022893455953
c = 16947792380653343668183074418719189429237241437366092930083218707643531284331359041557134961815270258682795684022186373763539789618707429809410930104661863616531800497066024257733632977939092179342185663603369251482529295279126585001466395251284374970736807376806433944629258377318039254703920331585415058927
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = x^4 + x^3 + x^2 + x + 1997 - c 
x0 = f.small_roots(X=2^32, beta=0.4)[0]
t = x0
print("t: ", t)

有了 $t$ 之后还是两个式子

$c_2 \equiv \sum_{i=1}^{19} (m+t)^{i} \pmod q$

$c_3 \equiv \sum_{i=1}^{19} (m\cdot t)^{i} \pmod q$

一个是加，一个是乘，但是和第二题的思路想法还是一样的，$x=m$ 肯定是这两个式子的根，所以给他们用一下 $GCD$


def GCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return GCD(b, a % b)

N = 54743202946161502811856295720870810456365343228950644705855322505182442571262980076941089058115540911930788333918940031879968906218781504935426145280173361374496692033334841657192812883322298846746060682411659733228146767637511270445829110291022551957289461462065489646257622668554123931913354561022893455953
c2 = 55877575842944488536738260741145576196064055314256851119903269638247167570517
c3 = 24752910240512109387212015792618368998146452177596723408887013541065473659025
P.<x> = PolynomialRing(Zmod(N))
f1 = 1997
f2 = 1997
t = 4035619213
for i in range(1,20):
    f1 += (x+t)^i
    f2 += (x*t)^i
f1 -= c3
f2 -= c2
GCD(f1,f2)

然后我们会得到一个报错 ZZ_p: division by non-invertible element，为啥呢？因为式子是在模 $q$ 下的，我们是在模 $n$ 的，所以，我们在 GCD 里打印一下信息

def GCD(a, b):
    print(a.monic(),b)
    if(b == 0):
        return a.monic()
    else:
        return GCD(b, a % b)

# x + 3269720129929206172290888040434844631999790813495546199598567897695383065785748573999332043932451485440224772661966886881467981258459641224093108678852609207558615214018620184887996376816876194347015843720084751398190561322698085192313884948494127864886155782163938754041371595283348119372481511820252205397 10094707220555426811770578750536360201358369370657659611252294461972567760547511972856872356006689569965863946144471753575975482915039158199762685955836393286445719933816896842332176600699750306238028403548064414478902718240280054367062726220893659556097524038957925231227120070260148988432886582427556137193

我们看到报错前的最后一条信息，有一个 10094707220555426811770578750536360201358369370657659611252294461972567760547511972856872356006689569965863946144471753575975482915039158199762685955836393286445719933816896842332176600699750306238028403548064414478902718240280054367062726220893659556097524038957925231227120070260148988432886582427556137193 然后对他和 n 用一下 gcd

得到 112229749912829564829770165528493741966573684175830091030568865445070552505343

于是，拿到了 $q$

再来一遍


def GCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return GCD(b, a % b)

N = 112229749912829564829770165528493741966573684175830091030568865445070552505343
c2 = 55877575842944488536738260741145576196064055314256851119903269638247167570517
c3 = 24752910240512109387212015792618368998146452177596723408887013541065473659025
P.<x> = PolynomialRing(Zmod(N))
f1 = 1997
f2 = 1997
t = 4035619213
for i in range(1,20):
    f1 += (x+t)^i
    f2 += (x*t)^i
f1 -= c3
f2 -= c2
print(long_to_bytes(int(N-GCD(f1,f2).coefficients()[0])))

发现还不行，我们得到的是 $m%q$，估计 $m$ 大于 $q$，爆破一下（希望不会大太多）

q = 112229749912829564829770165528493741966573684175830091030568865445070552505343
m = int(q-GCD(f1,f2).coefficients()[0])
for i in range(2**25):
	m+=q
	flag = long_to_bytes(m)
	if b"flag" in flag:
		print(flag)


# b'flag{ShangPo>XiaPo<YaSiLeYiQianDuo}'

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com